package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * 0501.二叉搜索树中的众数
 *
 * 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
 *
 * 假定 BST 有如下定义：
 * ● 结点左子树中所含结点的值小于等于当前结点的值
 * ● 结点右子树中所含结点的值大于等于当前结点的值
 * ● 左子树和右子树都是二叉搜索树
 *
 * 如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。
 * 具体步骤如下：
 * 1. 这个树都遍历了，用map统计频率
 * 至于用前中后序哪种遍历也不重要，因为就是要全遍历一遍，怎么个遍历法都行，层序遍历都没毛病！
 * @author Liyc
 *
 * 是二叉搜索树
 * 既然是搜索树，它中序遍历就是有序的。
 * 遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。
 * @date 2024/1/12 15:05
 **/

public class Solution20 {

    /**
     * 递归法
     * @param root
     * @return
     */
    private ArrayList<Integer> result;
    private int maxValue;
    private int count;
    private TreeNode pre;
    public int[] findMode(TreeNode root) {
        result = new ArrayList<>();
        maxValue = 0;
        count = 0;
        pre = null;
        if (root == null) {
             return null;
        }

        findMode1(root);
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }
    public void findMode1(TreeNode root) {
        if (root == null) return;

        findMode1(root.left);
        int rootValue = root.val;
        if (pre == null || pre.val != rootValue) {
            count = 1;
        } else {
            count++;
        }
        if (maxValue < count) {
            result.clear();
            maxValue = count;
            result.add(rootValue);
        } else if (maxValue == count) {
            result.add(rootValue);
        }

        pre = root;
        findMode1(root.right);
    }

    /**
     * 迭代法
     * @param root
     * @return
     */
    public int[] findMode2(TreeNode root) {
        if (root == null) return null;
        ArrayList<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        int maxValue = 0;
        int count = 0;
        TreeNode pre = null;
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack.pop();
                int rootValue = node.val;

                if (pre == null || rootValue != pre.val) {
                    count = 1;
                } else {
                    count++;
                }

                if (maxValue < count) {
                    result.clear();
                    maxValue = count;
                    result.add(rootValue);
                } else if (maxValue == count) {
                    result.add(rootValue);
                }
                pre = cur;
                cur = cur.right;

            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}
